package com.bins.knowledge.point.algorithm;

import java.util.Arrays;

/**
 * 有 n 个小朋友站成一排，每个小朋友有一个评分 ratings[i]。
 * 你需要给每个小朋友分糖，规则：
 * 每人至少一颗糖
 * 评分更高的小朋友，必须比他相邻的小朋友分到更多糖
 * 目标：在满足规则的前提下，最少需要多少颗糖？
 */
public class Candy {

    /**
     * 每人先发 1 颗糖（满足“至少一颗”）
     * 从左往右扫描：如果右边评分 > 左边，则右边 = 左边 + 1
     * 从右往左扫描：如果左边评分 > 右边，且左边糖 ≤ 右边，则左边 = 右边 + 1
     */
    public static int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];

        Arrays.fill(candies, 1);

        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        System.out.println(Arrays.toString(ratings));
        System.out.println(Arrays.toString(candies));

        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        System.out.println(Arrays.toString(candies));

        // 计算总糖数
        int total = 0;
        for (int candy : candies) {
            total += candy;
        }

        return total;
    }

    public static void main(String[] args) {
        int[] ratings = {1, 0, 2};
        System.out.println("最少需要 " + candy(ratings) + " 颗糖");

        int[] ratings2 = {1, 2, 2};
        System.out.println("最少需要 " + candy(ratings2) + " 颗糖");
    }
}